package 图;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Deque;
/**
 * 宫水三叶 那个 题解  希望在 该方法  理解 之后 能看懂
 * 
 * iu
 * 创建图的 方式 ：
 * 1.邻接表 
 * 2.邻接矩阵
 * 3.链式前向星
 * 4.还有左程云 那种 哈希表 的建图 方法
 * 
 * 
 * 
 * @author I adore you
 *
 */
public class Graph {
/**
 * N 是 题中     给出 条件  比如 给你个  二维数组 martix [][]    from ->martix[0] to ->martix[1]  weight -> martix[2] 
 * 这里  N  就是 这个二维 数组   的 长度   N = martix.length
 * 
 * 
 * 
 * 
 * 建图  时:
 *  如果 有向图  的 直接 
 *                   add(martix[0],martix[1],martix[2]);
 *                   
 *                   
 * 无向图   :
 * add(martix[0],martix[1],martix[2]);
 * add(martix[1],martix[0],martux[2]);
 * 
 *遍历 链式向前星 图的结构  明天 写一下   今天先  脑补一下
 */
	
	
	
	
/**
 *        N 是 图中的节点数目    
 *      无向图 ：  则 边的个数 则为 M  为 2 * (N-1) ~ (N-1)*N
 *      有向图： M 为       N -1   ~       (N-1)*N  >>  2
 *      边界前者  是 所有的 点 连城 一条直线 的时候的情况
 *      边界后者   是  任何两点 都 有  一条边  (完全无向图)
 *      
 *      
 *      这样写 的话 空间 消耗会非常的 大      所以  怎么办   啊   直接  直接  M  = martix.length *2  实际 长度 对吧   
 *      
 *      就像 leetcode 2039  这道题 的 下面的 提示信息 包含 了 节点 和  边的  范围 而           
 *      宫水三叶  在初始化  数组的 时候 就啊是参照 这个 数据 范围进行初始化 的 就非常的 牛逼   写题的  细节 
 *      而且 她  还初始化 为 static 遮掩 就只加载一次 就会更快 
 *      
 *      下面 解决 一个 疑问 就是                      int  N;  int head[] = new int [N];
 *      你猜一下  head 的长度 是多少  :     0
 *      因为 这个时候 N 就是 零     0  啊     你对 一个  长度 为 0 的数组 进行操作  不报错才怪  
 *      所以 要先给 N  赋值 再去  new 才会 有 效果
 *      
 *      
 */ 
	int N ;
//	int M = N * 2;
//	int M = N * N; 最大情况    
	int M;
	int index;
	int head[];// = new int [N];  // 无向图
//	int head [] = new int [N];       有向图
	Edge edges[];// = new Edge[M];
	
	/**
	 * 如果日后 忘掉  本站 连接 https://www.bilibili.com/video/BV13r4y1X7a4?spm_id_from=333.337.search-card.all.click
	 * 其中 有位 博主 说          建图     就是  建边   好像 是有道理的   
	 * 这里 写一下                              链式向前星 的  建图       方式
	 * 左程云的 那个 哈希表的 建图 肯定是 有 他的 道理 的 但是 可能有些 繁琐 重复 的记录 有点
	 * @author I adore you
	 * 链式向前 星  （数组 模拟链表）  简单来说 就是 用 数组 代替 链表实现  的功能
	 *注意 这个 Edge 啊 没有  from 对吧  但是 多了  一个 next
	 *
	 */
	static class Edge{
		int to;    // from --> to  就是这个 意思 对吧
		int weight; // 边 权重
		int next = -1;   //  直接 初始化  为   -1  便于 后面  判断
		// 存储的 相邻边的 下标               注意 这是 下标 index 
//		 啥事 相邻边  相邻边 就是 from 节点 指向  多个 to 节点  形成的边  就是 相邻边 
	}
	void add(int from,int to ,int weight) {
		edges[index].to = to;
		edges[index].weight = weight;
//		  下面这两行 代码   好好脑补 那个图  进行理解 一下  很清晰的
		edges[index].next = head[from];
		head[from] = index++;		
	}
	
	
/**
 * 
 * @param martix      二维数组 存储的 边点的 信息 
 * @param MaxN       图中 节点的 个数  直接 传入一个 最大值 进来 就行  也就是 输入 样例 中 节点 的 最大 取值 
 */
	void initialGraph(int martix[][],int MaxN) {
		this.N = MaxN;
//		this.M = martix.length * 2;
		this.head = new int[N];
		int len = martix.length;
		this.M = len * 2 ;
		this.edges = new Edge[M];
		for(int i = 0;i < M ;i++) {
			edges[i] = new Edge();
		}
/**
 * 		for(int i = 0;i < M ;i++) {
			edges[i] = new Edge();
		}
		这样是 可以 但 没必要 直接 下面的  一个 循环里面 解决 就行了 没必要 再用两个 循环 
		效率
		edges[i] = new Edge();
		edges[i+len] = new Edge();
		精髓 不 精髓 
		细不细节  
		细你个 大头鬼 啊 
		还是省不掉 
		这一步骤    能想出 这 纯粹 是  对 这个 链式前向星 不够了解
 */
		Arrays.fill(head, -1);
		for(int i = 0;i < len;i++) {
//			edges[i] = new Edge();
//			edges[i+len] = new Edge();
			add(martix[i][0],martix[i][1],1);
			add(martix[i][1],martix[i][0],1);
		}
	}
	
	
	
	/**
	 *     traverse  遍历 
	 * @param head
	 * @param edges
	 * 
	 * 遍历的 时候  i 从 1  开始 还是从 0 开始 完全 取决 与   head 数组中 有没有 编号 为 0 的 节点
	 * 说实话  只要 对这个  head 数组 进行 理解 透彻   遍历 traverse 就简单了
	 * 
	 */
	void traverseGraph(int head[],Edge edges[]) {
		for(int i = 1 ;head[i] != -1 ;i++ ) {
			
		}
	}
	
	
/**
 *   这里  直接 不用传入 参数 因为  声明  的时候 声明的就是全局变量
 *   
 * 注意 宫水三叶 那个题解    求 最短路径 数组  dis []  的 时候  不用       HashSet 来防止重复的情况 
 * 而是 用 本身 这个 dis []  来 防止 重复  为啥 可以 这么 做 因为 这个 图 是         无权图   (边的 权值 一样 )    
 * 但是 对于 大多数 图来说  遍历的   时候  需要 一个 容器 来         判断 重复 情况
 * 这个 容器 可以  是 HashSet  或者 Boolean 数组 或者 int 数组 都可以   
 *   
 */
	void bfs  (int root) {
		Deque<Integer> queue = new ArrayDeque<>();
//		  先把 编号 为          零号        的  节点 加  进来  
		HashSet<Integer> set = new HashSet<>();
		queue.addLast(root);
		set.add(root);
		System.out.println(root);
/**
 *    queue.add();
 *    queue.poll();
 *    尽量 这样 写 
 *    queue.addFirst();
 *    queue.pollFirst();
 */
		while(!queue.isEmpty()) {
			int nodeNumber = queue.pollFirst();
//			System.out.println(nodeNumber);
			for(int edgeIndex = head[nodeNumber] ;edgeIndex != -1; edgeIndex = edges[edgeIndex].next ) {
				int to = edges[edgeIndex].to;
//				if(!set.contains(edges[edgeIndex].to)) {
//					System.out.println(edges[edgeIndex].to);
//					queue.addFirst(edges[edgeIndex].to);
//				}
				if(!set.contains(to)) {
					System.out.println(to);
					queue.addLast(to);
					set.add(to);
				}
			}
		}
	}	
	/**
	 * 图 的dfs  还是  要 多钻研 一下 
	 * 有很多 说法   在这里面 
	 * 
	 *  这依旧需要 一个  容器 来判断 是否 重复 遍历  避免 重复 遍历 
	 *  这里 依旧 采用 HashSet 
	 * @param root
	 * 
void dfs(int x){
	s[x] = true ;
	printf("%d\n",x);
	int i ;
	for(i = head[x];i != -1 ; i = Edges[i].next){
		if(!s[Edges[i].to])
			dfs(Edges[i].to);
	}    
	
	
	下面这个 是一个 错误的 例子
//	  我好像大致 知道 错误在哪 了   一会 脑补 一下
	HashSet<Integer> set = new HashSet<>(); 
	void dfs(int root) {
//		int next = head[root];
		if(head[root] == -1) {
		   return ;
		}
		
		for(int edgeIndex = head[root];edgeIndex != -1; edgeIndex = edges[edgeIndex].next) {
			   if(!set.contains(root)) {
				   System.out.println(root);
				   set.add(root);
				    dfs(edges[edgeIndex].to);
			   }
		}
//	   if(!set.contains(root)) {
//		   System.out.println(root);
//		   set.add(root);
//		    dfs(edges[next].to);
//		     next = edges[next].next;
//		    dfs(edges[next].to);
//	   }
		
	} 
	*/
	HashSet<Integer> visited = new HashSet<>();
	void dfs(int root) {
		visited.add(root);
		System.out.println(root);
/**
 * 上面 这两行 代码 真的 是精髓 啊 说实话  
 * 这就是思想    
 * 一定要  对比  原始 的 思路 进行对 比 为啥 要 这样 做 
 *踩坑 是 一种 无法避免的 过程 也是 一个 进步的  过程
 */
		for(int edgeIndex = head[root];edgeIndex !=-1;edgeIndex = edges[edgeIndex].next) {
			if(!visited.contains(edges[edgeIndex].to)) {
				dfs(edges[edgeIndex].to);
			}
		}
	}
	
	
	
	
	
	public static void main(String []args) {
		Graph graph = new Graph();
		int [][] martix = {{0,1},{1,2},{2,4},{3,4},{0,3},{0,2}};
////		graph.N = 5;
//		System.out.println(graph.edges.length);
//		for(int i = 0;i < martix.length;i++) {
////			  构建 无向图  
//			graph.add(martix[i][0],martix[i][1],1);
//			graph.add(martix[i][1],martix[i][0],1);
//		}
		Edge e = new Edge();
		System.out.println(e.next);
		graph.initialGraph(martix, 5);
		graph.bfs(0);
//		graph.dfs(0);

	}
	
}
